use std::ptr::{null, null_mut};
use std::rc::Rc;
const HASH_TABLE_NULL: *mut std::ffi::c_void = null_mut();
#[repr(C)]
struct HashTable {
    table: *mut *mut HashTableEntry,
    table_size: u32,
    hash_func: Option<HashTableHashFunc>,
    equal_func: Option<HashTableEqualFunc>,
    key_free_func: Option<HashTableKeyFreeFunc>,
    value_free_func: Option<HashTableValueFreeFunc>,
    entries: u32,
    prime_index: u32,
}
#[repr(C)]
struct HashTableIterator {
    hash_table: *mut HashTable,
    next_entry: *mut HashTableEntry,
    next_chain: u32,
}
#[repr(C)]
struct HashTableEntry {
    pair: HashTablePair,
    next: *mut HashTableEntry,
}
#[repr(C)]
struct HashTablePair {
    key: HashTableKey,
    value: HashTableValue,
}
type HashTableKey = *mut std::ffi::c_void;
type HashTableValue = *mut std::ffi::c_void;
type HashTableHashFunc = Option<fn(HashTableKey) -> u32>;
type HashTableEqualFunc = Option<fn(HashTableKey, HashTableKey) -> i32>;
type HashTableKeyFreeFunc = Option<fn(HashTableKey)>;
type HashTableValueFreeFunc = Option<fn(HashTableValue)>;
static HASH_TABLE_PRIMES: [u32; 24] = [
    193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869,
    3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457,
    1610612741,
];
const HASH_TABLE_NUM_PRIMES: usize = HASH_TABLE_PRIMES.len();
fn hash_table_allocate_table(hash_table: *mut HashTable) -> i32 {
    let mut new_table_size: u32;
    if (*hash_table).prime_index < HASH_TABLE_NUM_PRIMES {
        new_table_size = HASH_TABLE_PRIMES[(*hash_table).prime_index];
    } else {
        new_table_size = (*hash_table).entries * 10;
    }
    (*hash_table).table_size = new_table_size;
    (*hash_table).table = calloc(
        (*hash_table).table_size as usize,
        std::mem::size_of::<*mut HashTableEntry>(),
    ) as *mut *mut HashTableEntry;
    (if (*hash_table).table.is_null() { 0 } else { 1 }) as i32
}
fn hash_table_free_entry(hash_table: *mut HashTable, entry: *mut HashTableEntry) {
    unsafe {
        let pair = &(*entry).pair;
        if let Some(key_free_func) = (*hash_table).key_free_func {
            key_free_func(pair.key);
        }
        if let Some(value_free_func) = (*hash_table).value_free_func {
            value_free_func(pair.value);
        }
        libc::free(entry as *mut libc::c_void);
    }
}
fn hash_table_new(hash_func: HashTableHashFunc, equal_func: HashTableEqualFunc) -> *mut HashTable {
    let hash_table: *mut HashTable =
        unsafe { libc::malloc(std::mem::size_of::<HashTable>()) as *mut HashTable };
    if hash_table.is_null() {
        return ptr::null_mut();
    }
    unsafe {
        (*hash_table).hash_func = hash_func;
        (*hash_table).equal_func = equal_func;
        (*hash_table).key_free_func = None;
        (*hash_table).value_free_func = None;
        (*hash_table).entries = 0;
        (*hash_table).prime_index = 0;
    }
    if hash_table_allocate_table(hash_table) == 0 {
        unsafe {
            libc::free(hash_table as *mut libc::c_void);
        }
        return ptr::null_mut();
    }
    hash_table
}
fn hash_table_free(hash_table: *mut HashTable) {
    let mut rover: *mut HashTableEntry;
    let mut next: *mut HashTableEntry;
    let mut i: u32;
    for i in 0..(*hash_table).table_size {
        rover = *(*hash_table).table.offset(i as isize);
        while !rover.is_null() {
            next = (*rover).next;
            hash_table_free_entry(hash_table, rover);
            rover = next;
        }
    }
    libc::free((*hash_table).table as *mut libc::c_void);
    libc::free(hash_table as *mut libc::c_void);
}
fn hash_table_register_free_functions(
    hash_table: &mut HashTable,
    key_free_func: HashTableKeyFreeFunc,
    value_free_func: HashTableValueFreeFunc,
) {
    hash_table.key_free_func = key_free_func;
    hash_table.value_free_func = value_free_func;
}
fn hash_table_enlarge(hash_table: *mut HashTable) -> i32 {
    let mut old_table: *mut *mut HashTableEntry;
    let mut old_table_size: u32;
    let mut old_prime_index: u32;
    let mut rover: *mut HashTableEntry;
    let mut pair: *mut HashTablePair;
    let mut next: *mut HashTableEntry;
    let mut index: u32;
    let mut i: u32;
    old_table = (*hash_table).table;
    old_table_size = (*hash_table).table_size;
    old_prime_index = (*hash_table).prime_index;
    (*hash_table).prime_index += 1;
    if hash_table_allocate_table(hash_table) == 0 {
        (*hash_table).table = old_table;
        (*hash_table).table_size = old_table_size;
        (*hash_table).prime_index = old_prime_index;
        return 0;
    }
    for i in 0..old_table_size {
        rover = *old_table.add(i as usize);
        while !rover.is_null() {
            next = (*rover).next;
            pair = &mut (*rover).pair;
            index = ((*hash_table).hash_func.as_ref().unwrap()(pair.key) % (*hash_table).table_size)
                as u32;
            (*rover).next = *(*hash_table).table.add(index as usize);
            *(*hash_table).table.add(index as usize) = rover;
            rover = next;
        }
    }
    libc::free(old_table as *mut libc::c_void);
    1
}
fn hash_table_insert(hash_table: *mut HashTable, key: HashTableKey, value: HashTableValue) -> i32 {
    let mut rover: *mut HashTableEntry;
    let mut pair: *mut HashTablePair;
    let mut newentry: *mut HashTableEntry;
    let mut index: u32;
    unsafe {
        if ((*hash_table).entries * 3) / (*hash_table).table_size > 0 {
            if hash_table_enlarge(hash_table) == 0 {
                return 0;
            }
        }
        index = ((*hash_table).hash_func.unwrap())(key) % (*hash_table).table_size;
        rover = (*hash_table).table.add(index as usize).read();
        while !rover.is_null() {
            pair = &mut (*rover).pair;
            if ((*hash_table).equal_func.unwrap())((*pair).key, key) != 0 {
                if let Some(value_free_func) = (*hash_table).value_free_func {
                    value_free_func((*pair).value);
                }
                if let Some(key_free_func) = (*hash_table).key_free_func {
                    key_free_func((*pair).key);
                }
                (*pair).key = key;
                (*pair).value = value;
                return 1;
            }
            rover = (*rover).next;
        }
        newentry = libc::malloc(std::mem::size_of::<HashTableEntry>()) as *mut HashTableEntry;
        if newentry.is_null() {
            return 0;
        }
        (*newentry).pair.key = key;
        (*newentry).pair.value = value;
        (*newentry).next = (*hash_table).table.add(index as usize).read();
        (*hash_table).table.add(index as usize).write(newentry);
        (*hash_table).entries += 1;
        return 1;
    }
}
fn hash_table_lookup(hash_table: *mut HashTable, key: HashTableKey) -> HashTableValue {
    let mut rover: *mut HashTableEntry;
    let mut pair: *mut HashTablePair;
    let index: u32;
    unsafe {
        index = ((*hash_table).hash_func.unwrap())(key) % (*hash_table).table_size;
        rover = *(*hash_table).table.add(index as usize);
        while !rover.is_null() {
            pair = &mut (*rover).pair;
            if ((*hash_table).equal_func.unwrap())(key, (*pair).key) != 0 {
                return (*pair).value;
            }
            rover = (*rover).next;
        }
    }
    HASH_TABLE_NULL
}
fn hash_table_remove(hash_table: &mut HashTable, key: HashTableKey) -> i32 {
    let index = (hash_table.hash_func.unwrap())(key) % hash_table.table_size;
    let mut rover = &mut hash_table.table[index];
    let mut result = 0;
    while let Some(entry) = rover.as_mut() {
        if (hash_table.equal_func.unwrap())(key, entry.pair.key) != 0 {
            let entry_to_remove = *rover;
            *rover = entry_to_remove.next.take();
            hash_table_free_entry(hash_table, entry_to_remove);
            hash_table.entries -= 1;
            result = 1;
            break;
        }
        rover = &mut entry.next;
    }
    result
}
fn hash_table_num_entries(hash_table: &HashTable) -> u32 {
    hash_table.entries
}
fn hash_table_iterate(hash_table: &mut HashTable, iterator: &mut HashTableIterator) {
    iterator.hash_table = hash_table;
    iterator.next_entry = std::ptr::null_mut();
    for chain in 0..hash_table.table_size {
        if !hash_table.table[chain as usize].is_null() {
            iterator.next_entry = hash_table.table[chain as usize];
            iterator.next_chain = chain;
            break;
        }
    }
}
fn hash_table_iter_has_more(iterator: *mut HashTableIterator) -> bool {
    unsafe { !(*iterator).next_entry.is_null() }
}
fn hash_table_iter_next(iterator: &mut HashTableIterator) -> HashTablePair {
    let mut pair = HashTablePair {
        key: None,
        value: None,
    };
    let hash_table = unsafe { &*iterator.hash_table };
    if iterator.next_entry.is_null() {
        return pair;
    }
    let current_entry = unsafe { &*iterator.next_entry };
    pair = current_entry.pair.clone();
    iterator.next_entry = if !current_entry.next.is_null() {
        current_entry.next
    } else {
        let mut chain = iterator.next_chain + 1;
        iterator.next_entry = std::ptr::null_mut();
        while (chain as usize) < hash_table.table_size as usize {
            if !hash_table.table.offset(chain as isize).is_null() {
                iterator.next_entry = hash_table.table.offset(chain as isize);
                break;
            }
            chain += 1;
        }
        iterator.next_chain = chain;
        iterator.next_entry
    };
    pair
}
